package algorithm.tx;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * <p>
 * 概念：贪心算法又叫做贪婪算法，它在求解某个问题是，总是做出眼前最大利益。
 * 也就是说只顾眼前不顾大局，所以它是局部最优解。核心点：通过局部最优推出全局最优。
 * 1.某天早上公司领导找你解决一个问题，明天公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束时间，你怎么样安排才能使会议室最大利用？即安排最多场次的会议？
 * 现在我们怎么去贪？也就这个我们选择的贪心策略：、
 * 选时间最短：1-3，2~4,3~5,4~6
 * 按结束时间从小到大排序：首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开
 * 咱们来看思考题1：
 * 0点~9点：9点之前开始的会议都不行了。
 * 8点~10点
 * 10点~12点：12点
 * 8点~20点
 * 思路：
 * </p>
 *
 * @author liyi
 * @since 2024/4/18 10:41
 */
public class MeetingTest {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        List<Meeting> mettings = new ArrayList<Meeting>();
        int n = cin.nextInt();    //n个会议
        for (int i = 0; i < n; i++) {
            int start = cin.nextInt();
            int end = cin.nextInt();
            Meeting metting = new Meeting(i + 1, start, end);
            mettings.add(metting);
        }

        mettings.sort(null);
        int curTime = 0;        //当前的时间,从一天的0点开始,如果领导要求从8点开始 那curTime=8
        for (int i = 0; i < n; i++) {
            Meeting metting = mettings.get(i);
            if (metting.startTime >= curTime) {        //会议的开始时间比我们当前的要大 表示可以开
                System.out.println(metting.toString());
                curTime = metting.endTime;
            }
        }
    }
}

class Meeting implements Comparable<Meeting> {

    int meNum; // 编号
    int startTime; // 开始时间
    int endTime; // 结束时间

    public Meeting(int meNum, int startTime, int endTime) {
        super();
        this.meNum = meNum;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Meeting o) {
        if (this.endTime > o.endTime) {
            return 1;
        }
        return -1;
    }

    @Override
    public String toString() {
        return "Metting [meNum=" + meNum + ", startTime=" + startTime
                + ", endTime=" + endTime + "]";
    }

}

